package com.longshine.arthmetic;

import com.longshine.arthmetic.tree.SortTree;

/**
 * 可绘画的程序
 *  
 *
 * @classname   DrawableApp.java 
 * @author      YitianC
 * @version     Revision: 1.1,  Date: 2008/05/14 01:43:47  
 * @history     
 *              Mar 13, 2012 5:12:47 PM  
 *
 */
public class DrawableApp {

	private final int minDis = 35;//结点间最小距离,树中最底层的结点之间的距离
	private final int rowHeight = 80; 		//层与层之间的高度
	/**
	 * 
	 * 绘制树结构 
	 * 
	 * @param st
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 5:14:42 PM
	 */
	public void drawTree(SortTree st){
		Node root = st.getRoot();
		MainFrame.getFrame().init();
		//设置根结点　的位置
		root.setX(MainFrame.getFrame().getWidth()/2);
		root.setY(100);
		drawNode(root,this.getTreeHeight(st));
	}
	/**
	 * 
	 * 绘制树结点 
	 * 
	 * @param node    要绘制的结点
	 * @param height  结点的高度
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 5:14:56 PM
	 */
	public void drawNode(Node node,int height){
		if(node == null){
			return;
		}
		if(node.parent==null){
			
			MainFrame.getFrame().addDrawableGraphic(node);
			drawNode(node.left,height-1);
			drawNode(node.right,height-1);
		}
		else{
			int x = 0;
			int dis = (int) (minDis*Math.pow(2, height-1)/2);//+node.getRadius()/2;
			//得到调整后的dis
		//	dis = adjustDistance(node,dis,height);
			//根据dis和父结点得到当前结点的位置
			if(node.parent.left == node){
				x = (node.parent.getX()-dis);//-node.getRadius()/2);
			}else{
				x = (node.parent.getX()+dis);//+node.getRadius()/2);
			}
			int y = node.parent.getY()+rowHeight;
			node.setX(x);
			node.setY(y);
			//加入到要绘画的结构中
			MainFrame.getFrame().addDrawableGraphic(node);
			//继续绘制此结点的左结点
			drawNode(node.left,height-1);
			//继续绘制此结点的右结点
			drawNode(node.right,height-1);
		}
	}
	/**
	 * 
	 * 调整dis,设节点和父结点圆心x轴距离为dis 
	 * 
	 * @param node  要调整的结点
	 * @param dis  初始距离
	 * @return    调整后的距离
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 4:01:15 PM
	 */
	private int adjustDistance(Node node,int dis,int h){
		int pdis = (int) (minDis*Math.pow(2, h)/2)+node.getRadius()/2; //父结点的dis,公式为 pdis = 最小距离*２的(当前结点高度-1)次方+半径
		//当dis+ r>=pdis(r为结点半径)时，高度为h的一些结点可能会有一些重叠部分，显示效果不好,需要减小此结点的dis
		while(dis+node.getRadius()/2>=pdis){
			dis -= 2;
		}
		return dis;
	}
	/**
	 * 
	 * 取得树高度 
	 * 
	 * @param st
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 12:42:59 PM
	 */
	public int getTreeHeight(SortTree st){
		return this.getSubNodeHeight(st.getRoot(), st.getRoot()==null?0:1);
	}
	/**
	 * 
	 * 取得树结点数，不包括空结点 
	 * 
	 * @param st
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 12:43:13 PM
	 */
	public int getNodeCount(SortTree st){
		return this.getSubNodeCount(st.getRoot(), st.getRoot()==null?0:1);
	}
	/**
	 * 
	 * 取得子结点数目 
	 * 
	 * @param n
	 * @param total
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 5:28:32 PM
	 */
	public int getSubNodeCount(Node n,int total){
		if(n == null) return total;
		if(n.left!= null){
			total++;
			total = getSubNodeCount(n.left,total);
			
		}
		if(n.right!=null){
			total++;
			total = getSubNodeCount(n.right,total);
		}
		return total;
	}
	/**
	 * 
	 * 取得子结点深度 
	 * 
	 * @param n
	 * @param c
	 * @return
	 * @author      YitianC 
	 * @history 
	 *              YitianC Mar 13, 2012 5:28:07 PM
	 */
	public int getSubNodeHeight(Node n,int c){
		if(n == null) return c;
		if(n.left!=null||n.right!=null){
			c++;
		}
		int lc= getSubNodeHeight(n.left,c);
		int rc = getSubNodeHeight(n.right,c);
		return lc>rc?lc:rc;
	}
}
